﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace StringMatch.MatchAlgorithms
{
    public static class Knuth_Morris_Pratt
    {
        /// <summary>
        /// See http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
        /// </summary>
        /// <param name="pattern"></param>
        /// <param name="text"></param>
        /// <returns></returns>
        public static List<int> Match(string pattern, string text)
        {
            List<int> result = new List<int>();
            int m = 0;
            int i = 0;
            int[] FailureArray = KMPFailure(pattern);
            bool found;

            while (m + i < text.Length)
            {
                found = false;
                if (pattern[i] == text[m + i])
                {
                    if (i == (pattern.Length - 1))
                    {
                        found = true;
                        result.Add(m);
                    }
                    if (found)
                    {
                        m += i - FailureArray[i];
                        i = 0;
                    }
                    else
                        i++;
                }
                else
                {
                    m = m + i - FailureArray[i];
                    if (FailureArray[i] > -1)
                        i = FailureArray[i];
                    else
                        i = 0;
                }
            
            }
            return result;
        }

        /// <summary>
        /// See http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm#.22Partial_match.22_table_.28also_known_as_.22failure_function.22.29
        /// </summary>
        /// <param name="pattern"></param>
        /// <returns></returns>
        private static int[] KMPFailure(string pattern)
        {
            int[] result = new int[pattern.Length];

            int candidate = 0;
            result[0] = -1;
            result[1] = 0;
            for (int pos = 2; pos < pattern.Length; pos++)
            {
                if (pattern[pos - 1] == pattern[candidate])
                {
                    candidate++;
                    result[pos] = candidate;
                }
                else if (candidate > 0)
                    candidate = result[candidate];
                else
                    result[pos] = 0;
            }

            return result;
        }
    }
}
